home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / dict / dic_test.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  5KB  |  203 lines
  1.  
  2. #include <LEDA/dictionary.h>
  3.  
  4. #include <LEDA/impl/ch_hash.h>
  5. #include <LEDA/impl/ch_hash1.h>
  6. #include <LEDA/impl/dp_hash.h>
  7. #include <LEDA/impl/avl_tree.h>
  8. #include <LEDA/impl/bin_tree.h>
  9. #include <LEDA/impl/rs_tree.h>
  10. #include <LEDA/impl/rb_tree.h>
  11. #include <LEDA/impl/skiplist.h>
  12. #include <LEDA/impl/ab_tree.h>
  13. #include <LEDA/impl/bb_tree.h>
  14.  
  15.  
  16. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  17. declare3(_dictionary,int,int,ch_hash)
  18. declare3(_dictionary,int,int,ch_hash1)
  19. declare3(_dictionary,int,int,dp_hash)
  20. declare3(_dictionary,int,int,avl_tree)
  21. declare3(_dictionary,int,int,bin_tree)
  22. declare3(_dictionary,int,int,rb_tree)
  23. declare3(_dictionary,int,int,rs_tree)
  24. declare3(_dictionary,int,int,skiplist)
  25. declare3(_dictionary,int,int,ab_tree)
  26. declare3(_dictionary,int,int,bb_tree)
  27.  
  28. declare3(_dictionary,float,float,avl_tree)
  29. declare3(_dictionary,float,float,bin_tree)
  30. declare3(_dictionary,float,float,rb_tree)
  31. declare3(_dictionary,float,float,rs_tree)
  32. declare3(_dictionary,float,float,skiplist)
  33. declare3(_dictionary,float,float,ab_tree)
  34. declare3(_dictionary,float,float,bb_tree)
  35. #endif
  36.  
  37.  
  38. void dic_test(dictionary<int,int>& D, int N, int* A, char* name)
  39. { 
  40.   cout << string("%-12s",name);
  41.   cout.flush();
  42.  
  43.   float T;
  44.   float T0 = T = used_time();
  45.  
  46.   for(int i=0; i<N; i++)  D.insert(A[i],0);
  47.   cout << string("%10.2f",used_time(T));
  48.   cout.flush();
  49.  
  50.   for(i=0; i<N; i++)  
  51.   { dic_item it = D.lookup(A[i]);
  52.     if (it == nil || D.key(it) != A[i]) error_handler(1,"error in lookup");
  53.    }
  54.  
  55.   cout << string("%10.2f",used_time(T));
  56.   cout.flush();
  57.  
  58.   for(i=0; i<N; i++)  D.del(A[i]);
  59.   cout << string("%10.2f",used_time(T));
  60.  
  61.   cout << string("%10.2f",used_time(T0));
  62.  
  63.   if (!D.empty()) cout << " NOT EMPTY !!\n";    
  64.  
  65.   newline;
  66.  
  67.   memory_clear();
  68.  
  69. }
  70.  
  71.  
  72. void dic_test(dictionary<float,float>& D, int N, float* A, char* name)
  73. { 
  74.   cout << string("%-12s",name);
  75.   cout.flush();
  76.  
  77.   D.clear();
  78.  
  79.   float T;
  80.   float T0 = T = used_time();
  81.  
  82.  
  83.   for(int i=0; i<N; i++)  D.insert(A[i],0);
  84.   cout << string("%10.2f",used_time(T));
  85.   cout.flush();
  86.  
  87.   for(i=0; i<N; i++)  D.lookup(A[i]);
  88.   cout << string("%10.2f",used_time(T));
  89.   cout.flush();
  90.  
  91.   for(i=0; i<N; i++)  D.del(A[i]);
  92.   cout << string("%10.2f",used_time(T));
  93.  
  94.   cout << string("%10.2f",used_time(T0));
  95.   newline;
  96.  
  97.   memory_clear();
  98. }
  99.  
  100.  
  101.  
  102. main()
  103. {
  104.  
  105. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  106.   _dictionary<int,int,ch_hash> CHH_DIC;
  107.   _dictionary<int,int,ch_hash1> CH1_DIC;
  108.   _dictionary<int,int,dp_hash> DPH_DIC;
  109.  
  110.   _dictionary<int,int,avl_tree> AVL_DIC;
  111.   _dictionary<int,int,bin_tree> BIN_DIC;
  112.   _dictionary<int,int,rb_tree>  RB_DIC;
  113.   _dictionary<int,int,rs_tree>  RS_DIC;
  114.   _dictionary<int,int,skiplist> SK_DIC;
  115.   _dictionary<int,int,bb_tree>  BB_DIC;
  116.   _dictionary<int,int,ab_tree>  AB_DIC;
  117.  
  118.   _dictionary<float,float,avl_tree> AVL_DIC1;
  119.   _dictionary<float,float,bin_tree> BIN_DIC1;
  120.   _dictionary<float,float,rb_tree>  RB_DIC1;
  121.   _dictionary<float,float,rs_tree>  RS_DIC1;
  122.   _dictionary<float,float,skiplist> SK_DIC1;
  123.   _dictionary<float,float,bb_tree>  BB_DIC1;
  124.   _dictionary<float,float,ab_tree>  AB_DIC1;
  125. #else
  126.   _dictionary(int,int,ch_hash) CHH_DIC;
  127.   _dictionary(int,int,ch_hash1) CH1_DIC;
  128.   _dictionary(int,int,dp_hash) DPH_DIC;
  129.  
  130.   _dictionary(int,int,avl_tree) AVL_DIC;
  131.   _dictionary(int,int,bin_tree) BIN_DIC;
  132.   _dictionary(int,int,rb_tree)  RB_DIC;
  133.   _dictionary(int,int,rs_tree)  RS_DIC;
  134.   _dictionary(int,int,skiplist) SK_DIC;
  135.   _dictionary(int,int,bb_tree)  BB_DIC;
  136.   _dictionary(int,int,ab_tree)  AB_DIC;
  137.  
  138.   _dictionary(float,float,avl_tree) AVL_DIC1;
  139.   _dictionary(float,float,bin_tree) BIN_DIC1;
  140.   _dictionary(float,float,rb_tree)  RB_DIC1;
  141.   _dictionary(float,float,rs_tree)  RS_DIC1;
  142.   _dictionary(float,float,skiplist) SK_DIC1;
  143.   _dictionary(float,float,bb_tree)  BB_DIC1;
  144.   _dictionary(float,float,ab_tree)  AB_DIC1;
  145. #endif
  146.  
  147.   int    N     = read_int("# keys = ");
  148.   int*   Int   = new int[N];
  149.   int*   Int1  = new int[N];
  150.   float* Float = new float[N];
  151.  
  152.   //init_random(N);
  153.  
  154.   for(int i=0; i<N; i++) Float[i] = Int[i] = random(0,10000000);
  155.  
  156.   for(i=0; i<N; i++) Int1[i] = i;
  157.  
  158.  
  159.   newline;
  160.   cout << "                insert    lookup    delete     total\n";
  161.   newline;
  162.  
  163.  
  164.  
  165.   dic_test(CHH_DIC,N,Int,"ch_hash");
  166.   dic_test(CH1_DIC,N,Int,"ch_hash1");
  167.   dic_test(DPH_DIC,N,Int,"dp_hash");
  168.   newline;
  169.   dic_test(SK_DIC,N,Int,"skiplist");
  170.   dic_test(RS_DIC,N,Int,"rs_tree");
  171.   dic_test(BIN_DIC,N,Int,"bin_tree");
  172.   dic_test(RB_DIC,N,Int,"rb_tree");
  173.   dic_test(AVL_DIC,N,Int,"avl_tree");
  174.   dic_test(BB_DIC,N,Int,"bb_tree");
  175.   dic_test(AB_DIC,N,Int,"ab_tree");
  176.   newline;
  177.  
  178.   dic_test(DPH_DIC,N,Int1,"dp_hash");
  179.   newline;
  180.   dic_test(SK_DIC,N,Int1,"skiplist");
  181.   dic_test(RS_DIC,N,Int1,"rs_tree");
  182.   //dic_test(BIN_DIC,N,Int1,"bin_tree");
  183.   dic_test(RB_DIC,N,Int1,"rb_tree");
  184.   dic_test(AVL_DIC,N,Int1,"avl_tree");
  185.   dic_test(BB_DIC,N,Int1,"bb_tree");
  186.   dic_test(AB_DIC,N,Int1,"ab_tree");
  187.   newline;
  188.  
  189.  
  190.   dic_test(RB_DIC1,N,Float,"rb_tree");
  191.   dic_test(AVL_DIC1,N,Float,"avl_tree");
  192.   dic_test(SK_DIC1,N,Float,"skiplist");
  193.   dic_test(RS_DIC1,N,Float,"rs_tree");
  194.   dic_test(BIN_DIC1,N,Float,"bin_tree");
  195.   dic_test(BB_DIC1,N,Float,"bb_tree");
  196.   dic_test(AB_DIC1,N,Float,"ab_tree");
  197.   newline;
  198.  
  199.   return 0;
  200. }
  201.  
  202.  
  203.